import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.FileWriter;
import java.util.*;

public class Demo3 {

    // 493. 翻转对
    int[] tmp;
    public int reversePairs(int[] nums) {
        tmp = new int[nums.length];
        return merge(nums, 0, nums.length - 1);
    }

    private int merge(int[] nums, int left, int right) {
        if(left >= right) return 0;

        // 1. 根据中间元素，将区间分为2部分， 并求出左右两个区间的翻转对
        int mid = (left + right) / 2, ret = 0;
        ret += merge(nums, left, mid);
        ret += merge(nums, mid + 1, right);

        // 2. 处理一左一右的情况，计算翻转对
        for(int cur1 = left, cur2 = mid + 1; cur1 <= mid && cur2 <= right; ) {
            if(nums[cur1] / 2.0 <= nums[cur2]) cur2++;
            else {
                ret += right - cur2 + 1;
                cur1++;
            }
        }

        int k = left, i = left, j = mid + 1;
        while(i <= mid && j <= right) {         // 数组降序的情况
            if(nums[i] >= nums[j]) tmp[k++] = nums[i++];
            else tmp[k++] = nums[j++];
        }
        while(i <= mid)  tmp[k++] = nums[i++];
        while(j <= right) tmp[k++] = nums[j++];

        // 将原数组排序
        while(left <= right) nums[left] = tmp[left++];
        return ret;

    }



    //160. 相交链表
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int len1 = 0, len2 = 0;
        ListNode longHead = headA, shortHead = headB;
        while(longHead != null) {
            len1++;
            longHead = longHead.next;
        }
        while(shortHead != null) {
            len2++;
            shortHead = shortHead.next;
        }

        longHead = headA; shortHead = headB;
        int len = len1 - len2;
        if(len1 < len2) {
            longHead = headB;
            shortHead = headA;
            len = len2 - len1;
        }

        while(len-- > 0) longHead = longHead.next;
        while(longHead != null && shortHead != null && longHead != shortHead) {
            longHead = longHead.next;
            shortHead = shortHead.next;
        }
        return longHead;
    }



    //34. 在排序数组中查找元素的第一个和最后一个位置
    public int[] searchRange(int[] nums, int target) {
        int[] ret = {-1, -1};
        int left = 0, right = nums.length - 1, mid, n = nums.length;
        if(n == 0) return ret;
        // 寻找左端点
        while(left < right) {
            mid = left + (right - left) / 2;
            if(nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        if(nums[left] == target) ret[0] = left;

        // 寻找右端点
        for(left = 0, right = nums.length - 1; left < right; ) {
            mid = left + (right - left + 1) / 2;
            if(nums[mid] > target) right = mid - 1;
            else left = mid;
        }
        if(nums[left] == target) ret[1] = left;
        return ret;
    }



    //230. 二叉搜索树中第K小的元素
    int count, ret = -1;
    public int kthSmallest(TreeNode root, int k) {
        count = k;
        inOrder(root);
        return ret;
    }
    private void inOrder(TreeNode root) {
        if(root == null) return;

        if(count > 0) inOrder(root.left);
        if(--count == 0) {
            ret = root.val;
        }
        if(count > 0) inOrder(root.right);
    }




    //111. 二叉树的最小深度
    public int minDepth(TreeNode root) {
        if(root == null) return 0;

        int lH = minDepth(root.left);
        int rH = minDepth(root.right);

        if(lH != 0 && rH != 0) return Math.min(lH, rH) + 1;
        if(lH != 0) return lH + 1;
        return rH + 1;
    }

    //104. 二叉树的最大深度
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;

        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }



    //260. 只出现一次的数字 III
    public int[] singleNumber(int[] nums) {
        int product = 0;
        for(int x : nums) product ^= x;

        // 两个不同的数进行异或，其结果在内存中一定存在一个比特位为 1
        // 取出内存中最右边的 1
        int k = product & (-product);
        int ret = 0;
        for(int x : nums) {
            if((x & k) != 0) ret ^= x;
        }
        return new int[]{ret, product ^ ret};
    }



    //1. 两数之和
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> hash = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            int x = target - nums[i];
            if(hash.containsKey(x)) {
                return new int[]{i, hash.get(x)};
            }else {
                hash.put(nums[i], i);
            }
        }
        return null;
    }


    // 151. 反转字符串中的单词
    public String reverseWords(String s) {
        char[] arr = new char[s.length()];
        int right = -1;
        // 1. 将字符串 s 转换为数组并去除前导、单词之间多余的空格和尾随空格
        for(int i = 0; i < s.length(); ) {
            while(i < s.length() && s.charAt(i) == ' ') i++;
            // 当字符串后面还有单词且当前单词不是第一个的情况下，将 right位置 置为 ' '
            if(right != -1 && i < s.length())  arr[++right] = ' ';
            while(i < s.length() && s.charAt(i) != ' ') arr[++right] = s.charAt(i++);
        }

        int len = right + 1, left = 0;
        // 2. 反转整个有效数组
        reverse(arr, 0, right);
        right = 0;

        // 3. 找到每个单词开始的结束位置，逐个进行翻转
        while(right < len) {
            while(right < len && arr[right] != ' ') right++;
            reverse(arr, left, right - 1);
            left = right = right + 1;
        }
        return new String(arr, 0, len);
    }
    private void reverse(char[] arr, int left, int right) {
        while(left < right) {
            char tmp = arr[left];
            arr[left++] = arr[right];
            arr[right--] = tmp;
        }
    }

 

    //239. 滑动窗口最大值
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length, left = 0, right = 0, pos = 0;
        if(n < k) return new int[0];
        int[] ret = new int[n - k + 1];
        Deque<Integer> q = new ArrayDeque<>();

        while(right < n) {
            if(q.isEmpty()) q.addFirst(nums[right]);
            else {
                if(nums[right] > q.peekFirst()) {
                    while(!q.isEmpty()) q.pollFirst();
                    q.addFirst(nums[right]);
                } else if(nums[right] <= q.peekLast()) {
                    q.addLast(nums[right]);
                }else{
                    while(nums[right] > q.peekLast()) q.pollLast();
                    q.addLast(nums[right]);
                }
            }
            if(right - left + 1 == k) {
                ret[pos++] = q.peekFirst();
                if(nums[left++] == q.peekFirst()) q.pollFirst();
            }
            right++;
        }
        return ret;
    }



    //LCR 186. 文物朝代判断
    public boolean checkDynasty(int[] places) {
        int[] hash = new int[14];
        int max = -1, min = 14;
        for(int x : places) {
            hash[x]++;
            if(x != 0 && hash[x] > 1) return false;
            if(x > max) max = x;
            if(x != 0 && x < min) min = x;
            if(max - min > 4) return false;
        }

        return true;
    }



    //LCR 187. 破冰游戏
    public static int iceBreakingGame(int num, int target) {
        Queue<Integer> q = new LinkedList<>();
        for(int i = 0; i < num; i++) q.offer(i);

        while(q.size() > 1) {
            int sz = q.size();
            for(int i = target >= sz ? (target - 1) % sz : target - 1; i > 0; i--) {
                q.offer(q.poll());
            }
            System.out.print(q.poll() + " ");
        }
        return q.peek();
    }



    //121. 买卖股票的最佳时机
    public int maxProfit(int[] prices) {
        int min = 10001, ret = 0;
        for(int x : prices) {
            if(x <= min) min = x;
            else ret = Math.max(ret, x - min);
        }
        return ret;
    }


    //LCR 189. 设计机械累加器
    public int mechanicalAccumulator(int target) {
        boolean flag = target == 0 || (target += mechanicalAccumulator(target - 1)) < 0;
        return target;
    }


    //LCR 190. 加密运算
    public int encryptionCalculate(int dataA, int dataB) {
        do {
            int carry = (dataA & dataB) << 1;
            dataA ^= dataB;
            dataB = carry;
        } while(dataB != 0);
        return dataA;
    }


    //LCR 191. 按规则计算统计结果
    public int[] statisticalResult(int[] nums) {
        int n = nums.length;
        if(n == 0) return new int[0];

        int[] f = new int[nums.length];
        int[] g = new int[nums.length];
        f[0] = 1; g[nums.length - 1] = 1;
        // 计数前 i 项元素的积
        for(int i = 1; i < nums.length; i++)
            f[i] = f[i-1] * nums[i-1];
        // 计算后 i 项元素的积
        for(int i = nums.length - 2; i >= 0; i--)
            g[i] = g[i+1] * nums[i+1];
        // 利用前缀积和后缀积 计算结果
        int[] ret = new int[nums.length];
        for(int i = 0; i < nums.length; i++) ret[i] = f[i] * g[i];
        return ret;
    }




    //8. 字符串转换整数 (atoi)
    public int myAtoi(String s) {
        //跳过字符串前面的空格
        int i = 0;
        for(; i < s.length(); i++) {
            if(s.charAt(i) != ' ') break;
        }

        if(i == s.length()) return 0;
        // 判断转换后整数的符号
        int flag = 1;       // 记录 该整数 是正数还是负数
        if(s.charAt(i) == '-') {
            flag = -flag;
            i++;
        } else if(s.charAt(i) == '+') {
            i++;
        } else if(!Character.isDigit(s.charAt(i))) {
            return 0;
        }

        // 开始 将连续的数字字符转换为 整数
        int ret = 0;
        while(i < s.length() && Character.isDigit(s.charAt(i))) {
            int tmp = (int) (s.charAt(i) - '0') ;
            // 判断为正数时， 反转结果是否 超出 int 的最大值
            if(ret > 214748364 || ret == 214748364 && tmp > 7 ) return 2147483647;
            // 判断为负数时， 反转结果是否 超出 int 的最大值
            if(ret < -214748364 || ret == -214748364 && tmp > 8) return -2147483648;
            ret = ret * 10 + tmp * flag;
            i++;
        }

        return ret;
    }




    //235. 二叉搜索树的最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;
        if(root == p || root == q) return root;

        TreeNode leftTree = lowestCommonAncestor(root.left, p, q);
        TreeNode rightTree = lowestCommonAncestor(root.right, p, q);
        if(leftTree != null && rightTree != null) return root;
        if(leftTree != null) return leftTree;
        return rightTree;
    }
}
